{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Time Needed to Inform All Employees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numOfMinutes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通知所有员工所需的时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>公司里有 <code>n</code> 名员工，每个员工的 ID 都是独一无二的，编号从 <code>0</code> 到 <code>n - 1</code>。公司的总负责人通过 <code>headID</code> 进行标识。</p>\n",
    "\n",
    "<p>在 <code>manager</code> 数组中，每个员工都有一个直属负责人，其中 <code>manager[i]</code> 是第 <code>i</code> 名员工的直属负责人。对于总负责人，<code>manager[headID] = -1</code>。题目保证从属关系可以用树结构显示。</p>\n",
    "\n",
    "<p>公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们，然后由这些下属通知他们的下属，直到所有的员工都得知这条紧急消息。</p>\n",
    "\n",
    "<p>第 <code>i</code> 名员工需要 <code>informTime[i]</code> 分钟来通知它的所有直属下属（也就是说在 <code>informTime[i]</code> 分钟后，他的所有直属下属都可以开始传播这一消息）。</p>\n",
    "\n",
    "<p>返回通知所有员工这一紧急消息所需要的 <strong>分钟数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, headID = 0, manager = [-1], informTime = [0]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>公司总负责人是该公司的唯一一名员工。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/08/graph.png\" style=\"height: 174px; width: 404px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>id = 2 的员工是公司的总负责人，也是其他所有员工的直属负责人，他需要 1 分钟来通知所有员工。\n",
    "上图显示了公司员工的树结构。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= headID &lt; n</code></li>\n",
    "\t<li><code>manager.length == n</code></li>\n",
    "\t<li><code>0 &lt;= manager[i] &lt; n</code></li>\n",
    "\t<li><code>manager[headID] == -1</code></li>\n",
    "\t<li><code>informTime.length&nbsp;== n</code></li>\n",
    "\t<li><code>0 &lt;= informTime[i] &lt;= 1000</code></li>\n",
    "\t<li>如果员工 <code>i</code> 没有下属，<code>informTime[i] == 0</code> 。</li>\n",
    "\t<li>题目 <strong>保证</strong> 所有员工都可以收到通知。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [time-needed-to-inform-all-employees](https://leetcode.cn/problems/time-needed-to-inform-all-employees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [time-needed-to-inform-all-employees](https://leetcode.cn/problems/time-needed-to-inform-all-employees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n0\\n[-1]\\n[0]', '6\\n2\\n[2,2,-1,2,2,2]\\n[0,0,1,0,0,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        memo = collections.defaultdict(list)\n",
    "        for i in range(len(manager)):\n",
    "            memo[manager[i]].append(i)\n",
    "            \n",
    "        res = 0\n",
    "        \n",
    "        def dfs(index, tmp):\n",
    "            nonlocal res\n",
    "            \n",
    "            if index not in memo.keys():\n",
    "                res = max(res, tmp)\n",
    "                return\n",
    "            \n",
    "            for subIndex in memo[index]:\n",
    "                dfs(subIndex, tmp+informTime[index])\n",
    "        \n",
    "        dfs(headID, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        mins = [0] * n\n",
    "        for i in range(n):\n",
    "            cur_i, cur_min = i, 0\n",
    "            # print(cur_i, end=' ')\n",
    "            while manager[cur_i] != -1:\n",
    "                cur_i = manager[cur_i]\n",
    "                # print(cur_i, end=' ')\n",
    "                cur_min += informTime[cur_i]\n",
    "            mins[i] = cur_min + mins[cur_i]\n",
    "            manager[i] = -1\n",
    "            # print(manager)\n",
    "            # print('min', cur_min)\n",
    "        return max(mins)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        mins = [0] * n\n",
    "        for i in range(n):\n",
    "            cur_i, cur_min = i, 0\n",
    "            # print(cur_i, end=' ')\n",
    "            while manager[cur_i] != -1:\n",
    "                cur_i = manager[cur_i]\n",
    "                # print(cur_i, end=' ')\n",
    "                cur_min += informTime[cur_i]\n",
    "            mins[i] = cur_min + mins[cur_i]\n",
    "            manager[i] = -1\n",
    "            # print(manager)\n",
    "            # print('min', cur_min)\n",
    "        return max(mins)\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes1(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        # 利用广度遍历，记录所有的最短路径\n",
    "        # 从head开始往下遍历,当informTime为0，则当前员工没有下属可通知，即它执行结束\n",
    "        # 从上往下遍历，构建管理-人员的map\n",
    "        from collections import defaultdict\n",
    "        map = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            map[manager[i]].append(i)\n",
    "        # 从headId开始遍历,并且按照最小堆的形式\n",
    "        res = 0\n",
    "        # 定义队列，第一维为时间，第二维为id,每个id只需要遍历一次即可，已遍历的则不需要了\n",
    "        que = [(0, headID)]\n",
    "        while que:\n",
    "            t, node = heapq.heappop(que)\n",
    "            # 如果当前通知之间为0，则表示到达支节点，进行汇总\n",
    "            # if informTime[node] == 0:\n",
    "            #     res = max(t, res)\n",
    "            # elif informTime[node] < 0:  # 表示当前节点已经访问过，不需要再次遍历了\n",
    "            #     continue\n",
    "            # else:\n",
    "            #     for r in map[node]:\n",
    "            #         heapq.heappush(que, (t + informTime[node], r))\n",
    "            # # 变成-1表示访问过\n",
    "            # informTime[node] *= -1\n",
    "            if node in map:\n",
    "                for r in map.pop(node):\n",
    "                    if informTime[r] == 0:\n",
    "                        res = max(res, t + informTime[node])\n",
    "                    else:\n",
    "                        heapq.heappush(que, (t + informTime[node], r))\n",
    "        return res\n",
    "\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        # 从下往上遍历，直接遍历到headID即结束，一个manager只有一条路径，故可以节省遍历时间\n",
    "        # 表示已经访问过的路径长度\n",
    "        visited = [0] * n\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            cur, total = i, 0\n",
    "            # 计算的时候进行剪枝\n",
    "            while manager[cur] != -1:\n",
    "                cur = manager[cur]\n",
    "                total += informTime[cur]\n",
    "            visited[i] = total + visited[cur]\n",
    "            manager[i] = -1\n",
    "            res = max(res, visited[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        mins = [0] * n\n",
    "        for i in range(n):\n",
    "            cur_i, cur_min = i, 0\n",
    "            # print(cur_i, end=' ')\n",
    "            while manager[cur_i] != -1:\n",
    "                cur_i = manager[cur_i]\n",
    "                # print(cur_i, end=' ')\n",
    "                cur_min += informTime[cur_i]\n",
    "            mins[i] = cur_min + mins[cur_i]\n",
    "            manager[i] = -1\n",
    "            # print(manager)\n",
    "            # print('min', cur_min)\n",
    "        return max(mins)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        for i, m in enumerate(manager):\n",
    "            if m < 0:\n",
    "                continue\n",
    "            s = 0\n",
    "            x = i\n",
    "            while manager[x] >= 0:\n",
    "                s += informTime[x]\n",
    "                x = manager[x]\n",
    "            s += informTime[x]\n",
    "\n",
    "            x = i\n",
    "            while manager[x] >= 0:\n",
    "                informTime[x], s = s, s - informTime[x]\n",
    "                manager[x], x = -1, manager[x]\n",
    "        \n",
    "        return max(informTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        manager[headID] = n\n",
    "        for i in range(n):\n",
    "            stack = [i]\n",
    "            while manager[stack[-1]] < n:\n",
    "                stack.append(manager[stack[-1]])\n",
    "            j = stack.pop()\n",
    "            while stack:\n",
    "                manager[stack[-1]] = manager[j] + informTime[j]\n",
    "                j = stack.pop()\n",
    "        \n",
    "        return max(manager) - n\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        mindis = [-1]*n\n",
    "        def getdis(mindis,manager,informTime,k):\n",
    "            if mindis[k]!=-1:\n",
    "                return mindis[k]\n",
    "            if manager[k]==-1:\n",
    "                mindis[k]=0\n",
    "                return 0\n",
    "            mindis[k]=getdis(mindis,manager,informTime,manager[k])+informTime[manager[k]]\n",
    "            return mindis[k]\n",
    "        for i in range(n):\n",
    "            getdis(mindis,manager,informTime,i)\n",
    "        print(mindis)\n",
    "        return max(mindis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        costOfTime = [0] * n\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            cost = 0\n",
    "            parent = manager[i]\n",
    "            while(parent != -1):\n",
    "                cost += informTime[parent]\n",
    "                parent = manager[parent]\n",
    "            ans.append(cost)\n",
    "        print(ans)\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int,\n",
    "                     manager: List[int], informTime: List[int]) -> int:\n",
    "        res = 0\n",
    "        visited = set()\n",
    "        for m in manager:\n",
    "            if m not in visited:\n",
    "                cur = m\n",
    "                t = 0\n",
    "                while cur != -1:\n",
    "                    visited.add(cur)\n",
    "                    t += informTime[cur]\n",
    "                    cur = manager[cur]\n",
    "                if res < t:\n",
    "                    res = t\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        Hash = {}\n",
    "        \n",
    "        for i in range(n):\n",
    "            temp_time = 0\n",
    "            k = i\n",
    "            while 1 == 1:\n",
    "                temp_time += informTime[k]\n",
    "                if not manager[k] in Hash:\n",
    "                    Hash[manager[k]] = temp_time\n",
    "                else:\n",
    "                    if Hash[manager[k]] < temp_time:\n",
    "                        Hash[manager[k]] = temp_time\n",
    "                    else:\n",
    "                        break\n",
    "                k = manager[k]\n",
    "                if k == -1:\n",
    "                    break\n",
    "\n",
    "        return Hash[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numOfMinutes(self, n, headID, manager, informTime):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type headID: int\n",
    "        :type manager: List[int]\n",
    "        :type informTime: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n==1:\n",
    "            return 0\n",
    "        dis_lsit= [0]*n\n",
    "        q= {i for i in range(n) if informTime[i] == 0}\n",
    "        while q:\n",
    "            tmp=q\n",
    "            q= set()\n",
    "            for yg in tmp:\n",
    "                dis_lsit[manager[yg]]=max(dis_lsit[manager[yg]],informTime[manager[yg]]+dis_lsit[yg])\n",
    "                if manager[yg]!=headID:\n",
    "                    q.add(manager[yg])\n",
    "\n",
    "\n",
    "        return dis_lsit[headID]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        # dic = collections.defaultdict(list)\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     dic[manager[i]].append(i)\n",
    "        \n",
    "        # visited = [0] * n\n",
    "        # for \n",
    "        # 从下属开始\n",
    "        em = []\n",
    "        st = set(manager)\n",
    "        # O(n)\n",
    "        for i in range(n):\n",
    "            if i not in st:\n",
    "                em.append(i)\n",
    "        visited = defaultdict(int)\n",
    "        time_max = 0\n",
    "        for e in em:\n",
    "            time = 0\n",
    "            while manager[e] != -1:\n",
    "                e = manager[e]\n",
    "                time += informTime[e]\n",
    "                if time <= visited[e]:\n",
    "                    break\n",
    "                else:\n",
    "                    visited[e] = time\n",
    "                print(e, time)\n",
    "            # time += informTime[headID]\n",
    "            time_max = max(time, time_max)\n",
    "        return time_max\n",
    "\n",
    "        # # 使用 defaultdict 来构建图\n",
    "        # g = collections.defaultdict(list)\n",
    "        # for i in range(n):\n",
    "        #     g[manager[i]].append(i)\n",
    "        \n",
    "        # def dfs(cur):\n",
    "        #     res = 0\n",
    "        #     # 遍历当前节点的邻居节点\n",
    "        #     for ne in g[cur]:\n",
    "        #         res = max(res, dfs(ne))\n",
    "        #     # 返回当前节点被通知需要的时间以及所有邻居节点被通知所需的最大时间\n",
    "        #     return informTime[cur] + res\n",
    "        \n",
    "        # # 从根节点开始进行 DFS 并返回总时间\n",
    "        # return dfs(headID)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        cur_max_time = 0\n",
    "        cur_list = [(headID, 0)]\n",
    "\n",
    "        manager_list = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if manager[i] !=-1:\n",
    "                manager_list[manager[i]].append(i)\n",
    "\n",
    "        while cur_list:\n",
    "            next_list = []\n",
    "            for cur_node,before_time in cur_list:\n",
    "                if before_time>cur_max_time:\n",
    "                    cur_max_time = before_time\n",
    "                for next_node in manager_list[cur_node]:\n",
    "                    next_list.append((next_node, before_time+informTime[cur_node]))\n",
    "            cur_list = next_list\n",
    "\n",
    "        return cur_max_time\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        dp = [0 for _ in range(n)]\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            fai = manager[i]\n",
    "            if fai >= 0:\n",
    "                graph[fai].append(i)\n",
    "        bossque = Queue()\n",
    "        bossque.put((headID,0))\n",
    "        ans = 0\n",
    "        while bossque.empty() == False:\n",
    "            now,step = bossque.get()\n",
    "            ans = max(ans, step)\n",
    "            for nxt in graph[now]:\n",
    "                bossque.put((nxt,step+informTime[now]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        # 构造树, 可以从manager找到所有的下属\n",
    "        from collections import defaultdict, deque\n",
    "        tree = defaultdict(list)\n",
    "\n",
    "        for i, mgr in enumerate(manager):\n",
    "            tree[mgr].append(i)\n",
    "\n",
    "        queue = deque([headID])\n",
    "\n",
    "        ans = 0\n",
    "        while len(queue) > 0:\n",
    "            for _ in range(len(queue)):\n",
    "                mgr = queue.popleft()\n",
    "                for sub in tree[mgr]:\n",
    "                    if informTime[sub] == 0:\n",
    "                        ans = max(ans, informTime[mgr])\n",
    "                    else:\n",
    "                        informTime[sub] += informTime[mgr]\n",
    "                        queue.append(sub)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        #解题思路：\n",
    "        #bfs\n",
    "\n",
    "        graph = [[] for _ in range(n)] #记录每个员工的下属\n",
    "        for i,leader in enumerate(manager):\n",
    "            if i == headID:\n",
    "                continue\n",
    "            graph[leader].append(i)\n",
    "        need_time = [inf] * n #通知到该员工的时间\n",
    "        need_time[headID] = 0\n",
    "        visit_list = [headID]\n",
    "        \n",
    "        while visit_list:\n",
    "            new_visit_list = []\n",
    "            for farther in visit_list:\n",
    "                for son in graph[farther]:\n",
    "                    need_time[son] = need_time[farther] + informTime[farther]\n",
    "                    new_visit_list.append(son)\n",
    "            visit_list = new_visit_list\n",
    "\n",
    "        return max(need_time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        depth = {headID:0}\n",
    "\n",
    "        for idx, m in enumerate(manager):\n",
    "            cur_depth = 0\n",
    "            while m != -1 and m not in depth:\n",
    "                cur_depth += informTime[m]\n",
    "                m = manager[m]\n",
    "            if m in depth:\n",
    "                depth[idx] = informTime[m] + depth[m] + cur_depth\n",
    "                res = max(res, depth[idx])\n",
    "\n",
    "            \n",
    "                \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        receiveTime = [ 0 for i in range(n) ]\n",
    "        child = [ [] for i in range(n) ]\n",
    "        for ch, fa in enumerate(manager):\n",
    "            if fa != -1:\n",
    "                child[fa].append(ch)\n",
    "\n",
    "        queue = [ headID ]\n",
    "        for cur in queue:\n",
    "            for to in child[cur]:\n",
    "                receiveTime[to] = receiveTime[cur] + informTime[cur]\n",
    "                queue.append(to)\n",
    "\n",
    "        return max(receiveTime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, m in enumerate(manager):\n",
    "            if m >= 0:\n",
    "                g[m].append(i)\n",
    "        ans = 0\n",
    "        def dfs(x, path_sum):\n",
    "            path_sum += informTime[x]\n",
    "            nonlocal ans\n",
    "            ans = max(ans, path_sum)\n",
    "            for y in g[x]:\n",
    "                dfs(y, path_sum)\n",
    "        dfs(headID, 0)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef numOfMinutes(self, n: int, headID: int, manager: list[int], informTime: list[int]) -> int:\n",
    "\t\tg = [[] for _ in range(n)]\n",
    "\t\t# 构造树\n",
    "\t\tfor i, m in enumerate(manager):\n",
    "\t\t\tif m >= 0:\n",
    "\t\t\t\tg[m].append(i)\n",
    "\t\tans=0\n",
    "\t\tdef dfs(x:int,max_path:int)->None:\n",
    "\t\t\tmax_path+=informTime[x]\n",
    "\t\t\tnonlocal ans\n",
    "\t\t\tans=max(ans,max_path)\n",
    "\t\t\tfor i in g[x]:\n",
    "\t\t\t\tdfs(i,max_path)\n",
    "\n",
    "\t\tdfs(headID, 0)\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        #广度优先搜索\n",
    "        g = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            g[manager[i]].append(i)\n",
    "        q = queue.Queue()\n",
    "        q.put((headID,0))\n",
    "        res = 0\n",
    "        while not q.empty():\n",
    "            idd,val = q.get()\n",
    "            if not g[idd]:\n",
    "                res = max(res,val)\n",
    "            else:\n",
    "                for ne in g[idd]:\n",
    "                    q.put((ne,val+informTime[idd]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        edges = defaultdict(dict)\n",
    "        for i in range(n):\n",
    "            if i != headID:\n",
    "                edges[manager[i]][i] = informTime[manager[i]]\n",
    "        queue, ans = deque([[headID, 0]]), 0\n",
    "        while queue:\n",
    "            curNode, preTime = queue.popleft()\n",
    "            for nextNode, nextTime in edges[curNode].items():\n",
    "                ans = max(ans, preTime + nextTime)\n",
    "                if nextNode in edges:\n",
    "                    queue.append([nextNode, preTime + nextTime])\n",
    "        return ans\n",
    "\n",
    "    def numOfMinutes2(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        # 单源最短路径\n",
    "        edges = defaultdict(dict)\n",
    "        for i in range(n):\n",
    "            if i != headID:\n",
    "                edges[manager[i]][i] = informTime[manager[i]]\n",
    "        visited = [False] * n\n",
    "        dist = [float(\"inf\")] * n\n",
    "        dist[headID] = 0\n",
    "        while False in visited:\n",
    "            # 在dist中找到未访问的最小距离的节点\n",
    "            x = -1\n",
    "            for i in range(n):\n",
    "                if (not visited[i] and x == -1) or (not visited[i] and dist[x] > dist[i]):\n",
    "                    x = i\n",
    "            # print(f\"x:{x}, dist:{dist}, visited:{visited}\")\n",
    "            visited[x] = True\n",
    "            # 松弛操作\n",
    "            for nextNode, val in edges[x].items():\n",
    "                if dist[x] + val < dist[nextNode]:\n",
    "                    dist[nextNode] = dist[x] + val\n",
    "        return max(dist)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        self.son = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if i != headID:\n",
    "                self.son[manager[i]].append(i)\n",
    "        \n",
    "        return self.dfs(headID, informTime)\n",
    "    \n",
    "    def dfs(self, u, informTime):\n",
    "        res = 0\n",
    "        for s in self.son[u]:\n",
    "            res = max(res, informTime[u] + self.dfs(s, informTime))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        for i in range (0,n):\n",
    "            if i!=headID:\n",
    "                g[manager[i]].append(i)\n",
    "        times=[0]*n\n",
    "        queue=[headID]\n",
    "        while queue:\n",
    "            m=len(queue)\n",
    "            for _ in range (0,m):\n",
    "                f=queue.pop(0)\n",
    "                for j in g[f]:\n",
    "                    times[j]=times[f]+informTime[f]\n",
    "                    queue.append(j)\n",
    "        return max(times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i, m in enumerate(manager):\n",
    "            if m != -1:\n",
    "                graph[m].append(i)\n",
    "\n",
    "        def dfs(cur):\n",
    "            count = 0\n",
    "            for i, m in enumerate(graph[cur]):\n",
    "                count = max(count, dfs(m))\n",
    "            return count + informTime[cur]\n",
    "\n",
    "        return dfs(headID)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        g = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            g[manager[i]].append(i)\n",
    "        def dfs(cur):\n",
    "            res = 0\n",
    "            for ne in g[cur]:\n",
    "                res = max(res, dfs(ne))\n",
    "            return res + informTime[cur]\n",
    "        return dfs(headID)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        def create_graph():\n",
    "            graph = defaultdict(list)\n",
    "            for i in range(n):\n",
    "                if i != headID:\n",
    "                    graph[manager[i]].append(i)\n",
    "            return graph\n",
    "\n",
    "        graph = create_graph()\n",
    "\n",
    "        def f(i: int) -> int:\n",
    "            if i not in graph:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for employee in graph[i]:\n",
    "                res = max(res, f(employee))\n",
    "            return res + informTime[i]\n",
    "\n",
    "        return f(headID)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\r\n",
    "        if n==1:\r\n",
    "            return 0\r\n",
    "        self.maxtime=0\r\n",
    "        son=dict()\r\n",
    "        manageridx=0\r\n",
    "        for i in range(n):\r\n",
    "            son[i]=[]\r\n",
    "        for i in range(len(manager)):\r\n",
    "            if manager[i]==-1:\r\n",
    "                manageridx=i\r\n",
    "            else:\r\n",
    "                son[manager[i]].append(i)\r\n",
    "        def check(person,time):\r\n",
    "            if not son[person]:\r\n",
    "                self.maxtime=max(self.maxtime,time)\r\n",
    "                return\r\n",
    "            else:\r\n",
    "                for sons in son[person]:\r\n",
    "                    check(sons,time+informTime[person])\r\n",
    "        check(manageridx,0)\r\n",
    "        return self.maxtime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        dic = {}\n",
    "        store = [None] * n \n",
    "        for i in range(len(manager)):\n",
    "            if manager[i] != -1:\n",
    "                if manager[i] not in dic:\n",
    "                    dic[manager[i]] = [i]\n",
    "                else:\n",
    "                    dic[manager[i]].append(i)\n",
    "        def dfs(cur) -> int:\n",
    "            if informTime[cur] == 0:\n",
    "                return 0\n",
    "            temp = -1\n",
    "            for i in dic[cur]:\n",
    "                temp = max(temp, dfs(i) + informTime[cur])\n",
    "            return temp\n",
    "        return dfs(headID)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        subs=defaultdict(list)\n",
    "        for i in range(n):\n",
    "            m=manager[i]\n",
    "            t=informTime[m]\n",
    "            subs[m].append((i,t))\n",
    "        q=deque([headID])\n",
    "        time=[inf]*n\n",
    "        time[headID]=0\n",
    "        ans=0\n",
    "        while q:\n",
    "            u=q.popleft()\n",
    "            for v,t in subs[u]:\n",
    "                time[v]=time[u]+t\n",
    "                q.append(v)\n",
    "        return max(time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        edges=defaultdict(list)\n",
    "        for i in range(n):\n",
    "            edges[manager[i]].append((informTime[i],i))\n",
    "        visited=[False]*n\n",
    "        dis=[inf]*n\n",
    "        dis[headID]=informTime[headID]\n",
    "        q=[(0,headID)]\n",
    "        while q:\n",
    "            _,u=heappop(q)\n",
    "            if visited[u]:\n",
    "                continue\n",
    "            visited[u]=True\n",
    "            for t,v in edges[u]:\n",
    "                dis[v]=min(dis[v],dis[u]+t)\n",
    "                heappush(q,(dis[v],v))\n",
    "        return max(dis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        # 本题可以理解为最底层员工到最上级领导的最远距离\n",
    "        # 求树的最大深度\n",
    "        # dfs\n",
    "        g = [[] for _ in range(n)]\n",
    "        d = [-1] * n\n",
    "        for i, x in enumerate(manager):\n",
    "            # 建图\n",
    "            if x != -1:\n",
    "                g[x].append(i)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if len(g[node]) == 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in g[node]:\n",
    "                res = max(res, dfs(i))\n",
    "            return informTime[node] + res\n",
    "        return dfs(headID)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        dp = [0] * n  # 用于存储每个员工被通知所需的最长时间\n",
    "\n",
    "        def dfs(employee):\n",
    "            if dp[employee] != 0:  # 如果已经计算过该员工的通知时间，则直接返回\n",
    "                return dp[employee]\n",
    "            \n",
    "            if manager[employee] == -1:  # 如果是总负责人，通知时间为0\n",
    "                dp[employee] = 0\n",
    "            else:\n",
    "                dp[employee] = dfs(manager[employee]) + informTime[manager[employee]]\n",
    "            \n",
    "            return dp[employee]\n",
    "\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        graph = collections.defaultdict(set)\n",
    "        for i, m in enumerate(manager):\n",
    "            graph[m].add(i)\n",
    "\n",
    "        queue = collections.deque([(headID, 0)])\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            n1, t1 = queue.popleft()\n",
    "            if graph[n1]:\n",
    "                t2 = t1 + informTime[n1]\n",
    "                ans = max(ans, t2)\n",
    "                for n2 in graph[n1]:\n",
    "                    queue.append((n2, t2))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        time = [0] * n\n",
    "        time[headID] = informTime[headID]\n",
    "        tree = {}\n",
    "        for idx, leader in enumerate(manager):\n",
    "            if leader not in tree:\n",
    "                tree[leader] = [idx]\n",
    "            else:\n",
    "                tree[leader].append(idx)\n",
    "\n",
    "        def broadcast(leader: int, subs: List[int]) -> None:\n",
    "            for sub in subs:\n",
    "                time[sub] += informTime[sub] + time[leader]\n",
    "                if informTime[sub] != 0:\n",
    "                    broadcast(sub, tree[sub])\n",
    "\n",
    "        broadcast(headID, tree[headID])\n",
    "        return max(time)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        def gettime(id): \n",
    "            #dfs，如果此员工被通知时间记录过\n",
    "            #直接返回，未记录过则该员工的被通知时间=他上级的被通知时间+和他上级的通知时间\n",
    "            if  id == headID:\n",
    "                return 0\n",
    "            if memo[id] !=0:\n",
    "                return memo[id]\n",
    "            return gettime(manager[id]) + informTime[manager[id]]\n",
    "\n",
    "        memo = [0] * n       \n",
    "        ans = 0\n",
    "        for i in range(n):  \n",
    "            #遍历每个员工，用memo数组记录每个员工被通知的时间\n",
    "            if i !=headID:   \n",
    "                memo[i] = gettime(i)\n",
    "                ans=max(ans,memo[i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "\n",
    "    def __init__(self, id, time=0):\n",
    "        self.id = id\n",
    "        self.time = time\n",
    "        self.children = []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        mapping = {}\n",
    "        for index in range(len(manager)):\n",
    "            if manager[index] == -1:\n",
    "                continue\n",
    "            if mapping.get(manager[index]) is None:\n",
    "                mapping[manager[index]] = [index]\n",
    "            else:\n",
    "                mapping[manager[index]].append(index)\n",
    "        head = TreeNode(headID)\n",
    "        q = [head]\n",
    "        while q:\n",
    "            temp = q\n",
    "            q = []\n",
    "            for node in temp:\n",
    "                for id in mapping.get(node.id, []):\n",
    "                    node.children.append(TreeNode(id, informTime[node.id]))\n",
    "                q += node.children\n",
    "        #print(head.children)\n",
    "        return self.count(head)\n",
    "\n",
    "    def count(self, node):\n",
    "        if node is None:\n",
    "            return 0\n",
    "        arg = []\n",
    "        for child in node.children:\n",
    "            arg.append(self.count(child))\n",
    "        print(arg)\n",
    "        if arg:\n",
    "            return node.time + max(arg)\n",
    "        else:\n",
    "            return node.time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,v,parent=None):\n",
    "        self.v=v\n",
    "        self.parent=parent\n",
    "        self.children=[]\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        nodes=[Node(i) for i in range(n)]\n",
    "        root=None\n",
    "        for i,p in enumerate(manager):\n",
    "            if p==-1:\n",
    "                root=nodes[i]\n",
    "                continue\n",
    "            nodes[i].parent=nodes[p]\n",
    "            nodes[p].children.append(nodes[i])\n",
    "        res=0\n",
    "        marked=set()\n",
    "        def dfs(node,r):\n",
    "            nonlocal res\n",
    "            marked.add(node.v)\n",
    "            res=max(res,r)\n",
    "            for cnode in node.children:\n",
    "                if not cnode.v in marked:\n",
    "                    dfs(cnode,r+informTime[node.v])\n",
    "        dfs(root,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        t = dict()\n",
    "        for i in range(n):\n",
    "            t[i] = set()\n",
    "\n",
    "        for key, value in enumerate(manager):\n",
    "            if value >= 0:\n",
    "                t[value].add(key)\n",
    "        dp = [0] * n\n",
    "        temp1 = {headID}\n",
    "        while temp1:\n",
    "            temp2 = set()\n",
    "            for te in temp1:\n",
    "                for te2 in t[te]:\n",
    "                    temp2.add(te2)\n",
    "                    dp[te2] += dp[te] + informTime[te]\n",
    "            temp1 = temp2\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        children = defaultdict(list)\n",
    "        for i in range(headID):\n",
    "            children[manager[i]].append(i)\n",
    "        for i in range(headID + 1, n):\n",
    "            children[manager[i]].append(i)\n",
    "        \n",
    "        dfs = lambda i: informTime[i] if not children[i] else max(dfs(j) for j in children[i]) + informTime[i]\n",
    "        return dfs(headID)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        edges1 = collections.defaultdict(list)\n",
    "        edges2 = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if manager[i] != -1:\n",
    "                edges1[i].append(manager[i])\n",
    "                edges2[manager[i]].append(i)\n",
    "\n",
    "        seq = list()\n",
    "        visited = set()\n",
    "        def dfs(node):\n",
    "            for i in edges2[node]:\n",
    "                if i in visited:\n",
    "                    continue\n",
    "                else:\n",
    "                    visited.add(i)\n",
    "                    dfs(i)\n",
    "            seq.append(node)\n",
    "\n",
    "        dfs(headID)\n",
    "        for i in seq[::-1]:\n",
    "            if i!=headID:\n",
    "                informTime[i] += max([informTime[a] for a in edges1[i]])\n",
    "        # print(informTime)\n",
    "        return max(informTime)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        graph = {i:set() for i in range(n)}\n",
    "\n",
    "        for i in range(len(manager)):\n",
    "            m = manager[i]\n",
    "            info = informTime[m]\n",
    "            if m == -1:\n",
    "                continue\n",
    "            graph[m].add((i, info))\n",
    "        queue = deque()\n",
    "        queue.append((headID, 0))\n",
    "        max_info_time = 0\n",
    "\n",
    "        while queue:\n",
    "            node, cur_info_time = queue.popleft()\n",
    "            for neighbor, info_time in graph[node]:\n",
    "                new_info_time = cur_info_time + info_time\n",
    "                if new_info_time > max_info_time:\n",
    "                    max_info_time = new_info_time\n",
    "                queue.append((neighbor, new_info_time))\n",
    "        \n",
    "        return max_info_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        subordinates = [set() for _ in range(n)]\n",
    "        for i, head in enumerate(manager):\n",
    "            if head >= 0:\n",
    "                subordinates[head].add(i)\n",
    "\n",
    "        def all_inform_time(id_):\n",
    "            if len(subordinates[id_]) == 0:\n",
    "                return 0\n",
    "            return max(all_inform_time(sub_id) for sub_id in subordinates[id_]) + informTime[id_]\n",
    "\n",
    "        return all_inform_time(headID)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val=None, child: List=[]) -> None:\n",
    "        self.val = val\n",
    "        self.child = child[:]\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        d = {i: Node(i) for i in range(n)}\n",
    "        for i in range(n):\n",
    "            if manager[i] != -1:\n",
    "                d[manager[i]].child.append(i)\n",
    "        \n",
    "        head = d[headID]\n",
    "        ans = 0\n",
    "        vis = set()\n",
    "        \n",
    "        def preOrder(root: Node, time):\n",
    "            nonlocal ans\n",
    "            vis.add(root.val)\n",
    "            if root:\n",
    "                time += informTime[root.val]\n",
    "                for child in root.child:\n",
    "                    if child not in vis:\n",
    "                        preOrder(d[child], time)\n",
    "            \n",
    "            ans = max(ans, time)\n",
    "\n",
    "        preOrder(head, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        fa = {i:set() for i in range(n)}\n",
    "        fa[-1] = set()\n",
    "        for i, v in enumerate(manager):\n",
    "            fa[v].add(i)\n",
    "\n",
    "        cost = [0]*n\n",
    "\n",
    "        q = set([headID])\n",
    "        visit = set()\n",
    "        while q:\n",
    "            new = set()\n",
    "            for pre in q:\n",
    "                for ne in fa[pre]:\n",
    "                    cost[ne] = cost[pre]+informTime[pre]\n",
    "                new |= fa[pre]\n",
    "            visit |= q\n",
    "            new -= visit\n",
    "            q = new\n",
    "\n",
    "        return max(cost)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class TreeNode(object):\n",
    "\n",
    "    def __init__(self, parent):\n",
    "        self.parent = parent\n",
    "        self.childs = list()\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "                0\n",
    "            1       2\n",
    "        3      4 5      6\n",
    "    '''\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        mapping = dict()\n",
    "        root = None\n",
    "        for i, p in enumerate(manager):\n",
    "            mapping[i] = TreeNode(p)\n",
    "            if p == -1:\n",
    "                root = i\n",
    "        for i, p in enumerate(manager):\n",
    "            if p != -1:\n",
    "                mapping[p].childs.append(i)\n",
    "        \n",
    "        result = 0\n",
    "        def dfs(root, val):\n",
    "            nonlocal result\n",
    "            val += informTime[root]\n",
    "            result = max(result, val)\n",
    "            for it in mapping[root].childs:\n",
    "                dfs(it, val)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return result\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        # dfs\n",
    "        lead = {}   # 员工x的下属\n",
    "        leader = -1 # 总负责人\n",
    "        for i, v in enumerate(manager):\n",
    "            if v==-1: leader = i\n",
    "            if str(v) not in lead: lead[str(v)]=[]\n",
    "            if v!=-1: lead[str(v)].append(i)\n",
    "       \n",
    "        @cache\n",
    "        def dfs(p:int):\n",
    "            nonlocal lead\n",
    "            # p 是底层员工, 不需要通知别人\n",
    "            if str(p) not in lead:\n",
    "                return 0\n",
    "            max_t = 0\n",
    "            for pp in lead[str(p)]:\n",
    "                max_t = max(max_t, informTime[p]+dfs(pp))\n",
    "            return max_t\n",
    "\n",
    "        return dfs(leader)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "       \n",
    "        @cache\n",
    "        def dfs(x: int) -> int:\n",
    "            if manager[x] >= 0:\n",
    "                informTime[x] += dfs(manager[x])\n",
    "                manager[x] = -1  # 标记 x 计算过\n",
    "            return informTime[x]\n",
    "\n",
    "        return max(dfs(i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        e = {i:set() for i in range(n)}\n",
    "        for i,m in enumerate(manager):\n",
    "            if m != -1:\n",
    "                e[m].add(i)\n",
    "        def dfs(h,t):\n",
    "            if not e[h]:return t\n",
    "            return max( dfs(x,t+informTime[h] )for x in e[h])\n",
    "        return dfs(headID,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        v=collections.defaultdict(set)\n",
    "        for i in range(n):\n",
    "            if manager[i]!=-1:\n",
    "                v[manager[i]].add(i)\n",
    "        def dfs(m,time):\n",
    "            if not v[m]:\n",
    "                return time\n",
    "            return max(dfs(k,time+informTime[m]) for k in v[m])\n",
    "        return dfs(headID,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        memo = {headID: 0}\n",
    "        res = 0\n",
    "        def dp(i):\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            m = manager[i]\n",
    "            memo[i] = dp(m) + informTime[m]\n",
    "            return memo[i]\n",
    "        for i in range(n):\n",
    "            if informTime[i] == 0: #只取叶节点\n",
    "                res = max(res, dp(i))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        e = {i:set() for i in range(n)}\n",
    "        for i,m in enumerate(manager):\n",
    "            if m != -1:\n",
    "                e[m].add(i)\n",
    "        @cache\n",
    "        def dfs(h,t):\n",
    "            if not e[h]:return t\n",
    "            return max( dfs(x,t+informTime[h] )for x in e[h])\n",
    "        return dfs(headID,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        # 自顶向下dfs,记忆化是无效的，超时\n",
    "        # def dfs(i):\n",
    "        #     if informTime[i] == 0: return 0\n",
    "        #     res = 0\n",
    "        #     for j,num in enumerate(manager):\n",
    "        #         if num == i:\n",
    "        #             res = max(res, dfs(j) + informTime[i])\n",
    "        #     return res\n",
    "        # return dfs(headID)\n",
    "        \n",
    "        # 返回从第i号员工，自底向上搜索的时间总和\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == -1: return 0 # manager[i] != -1，表示i与manager[i]相连，manager[i] == -1，表面i为根结点\n",
    "            return dfs(manager[i]) + informTime[i]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if informTime[i] == 0: # 剪枝，只从叶子结点开始向上搜索\n",
    "                res = max(res, dfs(i)) # 所有叶子结点得到消息的时间最大值即为 通知所有员工这一紧急消息所需要的 分钟\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 感觉这个做法其实有点无赖\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        # edges = collections.defaultdict(list)\n",
    "\n",
    "        @cache\n",
    "        def dfs(u: int) -> int:\n",
    "            return dfs(manager[u]) + informTime[u] if u != headID else informTime[u]\n",
    "\n",
    "            # if u != headID:\n",
    "            #     return dfs(manager[u]) + informTime[u]\n",
    "            # else:\n",
    "            #     return informTime[u]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, dfs(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        time = [0] * n\n",
    "        \n",
    "        @cache\n",
    "        def get(node):\n",
    "            if node == headID:\n",
    "                return 0\n",
    "            mgr = manager[node]\n",
    "            return get(mgr) + informTime[mgr]\n",
    "        \n",
    "        return max(get(x) for x in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n==-1:\n",
    "                return 0\n",
    "            return informTime[n]+dfs(manager[n])\n",
    "        ans=0\n",
    "        for i,x in enumerate(informTime):\n",
    "            if x==0:\n",
    "                ans=max(ans,dfs(i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n",
    "        # 使用缓存，存储每个节点到根节点的最长时间\n",
    "        @cache\n",
    "        def dfs(cur):\n",
    "            if cur == headID:  # 当前节点为根节点\n",
    "                return 0\n",
    "            # 递归遍历当前节点的直属上级节点，返回时间和\n",
    "            # 由于 informTime 存储的是当前节点通知下属所需时间，所以使用 manager[cur] 获取上级节点\n",
    "            return dfs(manager[cur]) + informTime[manager[cur]]\n",
    "        # 对所有节点遍历，返回最长时间\n",
    "        return max(dfs(i) for i in range(n))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
